
class ListNode:
    """链表节点"""
    def __init__(self, val):
        self.val = val
        self.next: ListNode | None =None



class stack_linked:
    """栈模拟，基于链表"""
    def __init__(self):
        self._peek: ListNode | None = None
        self._size = 0

    def size(self) -> int:
        """返回栈元素个数"""
        return self._size

    def is_empty(self) -> bool:
        """判断栈是否为空，空返回True"""
        return self.size == 0

    def push(self,val:int):
        """入栈"""
        node = ListNode(val)
        node.next = self._peek
        self._peek = node
        self._size += 1
        pass

    def pop(self) -> int:
        """出栈"""
        num = self.peek()
        self._peek = self._peek.next
        self._size -= 1
        return num

        pass

    def peek(self):
        """访问栈顶元素"""
        if self.is_empty():
            raise IndexError("栈为空")
        return self._peek.val
        pass

    def to_list(self) -> list[int]:
        arr:list[int] = []
        node = self._peek
        while node:
            arr.append(node.val)
            node = node.next
        arr.reverse()
        return arr



class ArrayStack:
    """栈模拟基于数组"""
    def __init__(self):
        self._stack:list[int] = []

    def size(self) -> int:
        """返回栈元素个数"""
        return len(self._stack)

    def is_empty(self):
        return self.size() == 0

    def pop(self):
        if self.is_empty():
            raise IndexError("栈为空")
        return self._stack.pop()

    def push(self, val):
        self._stack.append(val)

    def peek(self):
        return self._stack[-1]

    def to_list(self):
        return self._stack

class ArrayQueque:
    """基于数组实现队列"""
    def __init__(self):
        self._queque:list[int] = []

    def size(self):
        return len(self._queque)

    def is_empty(self):
        return self.size() == 0

    def push(self, val: int):
        self._queque.append(val)

    def pop(self):
        if self.is_empty():
            raise IndexError("栈为空")
        if self._queque.count(self._queque[-1]) == 1:
            val = self._queque[-1]
            print("remove")
            self._queque.remove(val)
            return val
        return self._queque.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("栈为空")
        return self._queque[0]

    def to_list(self):
        return self._queque

class LinkedQueque:
    """基于链表实现队列"""
    def __init__(self):
        self._front: ListNode | None = None
        self._next: ListNode | None = None
        self._size = 0

    def size(self):
        return self._size

    def is_empty(self):
        return self.size() == 0

    def push(self, val):
        node = ListNode(val)
        if self._front == None:
            self._front = node
            self._next = node

        else:
            self._next.next = node
            self._next = node
        self._size += 1

    def peek(self):
        if self.is_empty():
            raise IndexError("栈为空")
        return self._front.val

    def pop(self):
        if self.is_empty():
            raise IndexError("栈为空")
        node = self._front.val
        self._front = self._front.next
        return node

    def to_list(self):
        arr = []
        node = self._front
        while node:
            arr.append(node.val)
            node = node.next
        return arr


class ListNode:
    def __init__(self, val):
        self.val = val
        self._front: ListNode | None = None
        self._next: ListNode | None = None

class LinkedListDeque:
    def __init__(self):
        self._front: ListNode | None = None
        self._next: ListNode | None = None
        self._size = 0

    def size(self):
        return self._size

    def is_empty(self):
        return self.size() == 0

    def push(self, val, is_front: bool):
        node = ListNode(val)
        if is_front:
            if self.is_empty():
                self._front = node
                self._next = node
            else:
                self._front._front = node
                node._next = self._front
                self._front = node
        else:
            if self.is_empty():
                self._front = node
                self._next = node
            else:
                self._next._next = node
                node._front = self._next
                self._next = node
        self._size += 1

    def peek(self, is_front: bool):
        if is_front:
            if self.is_empty():
                raise IndexError("栈为空")
            return self._front.val
        else:
            if self.is_empty():
                raise IndexError("栈为空")
        return self._next.val

    def pop(self, is_front:  bool) -> int:

        if is_front:
            if self.is_empty():
                raise IndexError("栈为空")
            val = self._front.val
            node = self._front._next
            self._front = node
            node._front: ListNode | None = None

        else:
            if self.is_empty():
                raise IndexError("栈为空")
            val = self._next.val
            self._next = self._next._front
            self._next._next: ListNode | None = None
        self._size -= 1
        return val

    def to_list(self, is_front: bool):
        arr = []
        if is_front:
            node = self._front
            while node:
                arr.append(node.val)
                node = node._next
        else:
            node = self._next
            while node:
                arr.append(node.val)
                node = node._front
        return arr

class ArrayListDeeque:
    def __init__(self, capacity):
        self.arrayDeque:list[int] = [0] * capacity
        self._front = 0
        self._size = 0

    def capacity(self):
        return len(self.arrayDeque)

    def size(self):
        return self._size

    def is_empty(self):
        return self.size() == 0

    def index(self, i:int) -> int:
        return (i + self.capacity()) % self.capacity()

    def push(self, val, is_front):
        if self.is_empty():
            self.arrayDeque[self._front] = (val)
        elif is_front:
            if self.size() == self.capacity():
                print("双向队列已满")
                return
            self._front = self.index(self._front - 1)
            self.arrayDeque[self._front] = val
        else:
            if self.size() == self.capacity():
                print("双向队列已满")
                return
            self.arrayDeque[self.index(self._front + self._size)] = (val)
        self._size += 1

    def peek(self, is_front):
        if self.is_empty():
            raise IndexError("队列为空")
        elif is_front:
            return self.arrayDeque[self._front]
        else:
            return self.arrayDeque[-1]

    def pop(self, is_front):
        if self.is_empty():
            raise IndexError("队列为空")
        elif is_front:
            val = self.arrayDeque[self._front]
            self.arrayDeque[self._front] = 0
            self._front = self.index(self._front + 1)
        else:
            val = self.arrayDeque.pop()
        self._size -= 1
        return val

    def to_list(self):
        if self.is_empty():
            print("队列为空")
            return
        arr = []
        for i in range(0,self._size):
            index = self.index(self._front + i)
            arr.append(self.arrayDeque[index])
        return arr

class Pair:
    def __init__(self,key: int, val: str):
        self.key = key
        self.val = val



class ArrayHash:
    """哈希：基于数组的实现"""
    def __init__(self):
        self.bukets: list[Pair | None] = [None] * 100

    def hash_func(self, key: int):
        index = key % 100
        return index

    def get(self,key):
        index = self.hash_func(key)
        pair: Pair = self.bukets[index]
        if pair == None:
            return None
        return pair.val

    def put(self, key, val):
        index = self.hash_func(key)
        pair = Pair(key, val)
        self.bukets[index] = pair

    def remove(self, key):
        index = self.hash_func(key)
        self.bukets[index] = None

    def entry_set(self):
        result = []
        for i in self.bukets:
            if i != None:
                result.append(i)
        return result

    def key_set(self):
        result = []
        for i in self.bukets:
            if i != None:
                result.append(i.key)
        return result

    def value_set(self):
        result = []
        for i in self.bukets:
            if i != None:
                result.append(i.val)
        return result

    def print(self):
        for i in self.bukets:
            if i != None:
                print(i.key," -> ",i.val)

class ArraysHash:
    """哈希：解决哈希冲突之改良数据结构。

    把元素放在一个列表中，再把数组（列表）放在桶中"""
    def __init__(self):
        self._size = 0 #元素个数
        self.capacity = 4 #初始哈希表大小
        self.load_thres = 2.0 / 3.0 #负载因子，当元素个数 除 哈希表大小 大于负载因子时，将扩容
        self.extend_ratio = 2 # 每次扩容倍数
        self.buckets = [[] for _ in range(self.capacity)]

    def size(self):
        return self._size

    def hash_key(self, key: int) -> int:
        index = key % self.capacity
        return index

    def load_factor(self) -> bool:
        return self.size() / self.capacity > self.load_thres

    def put(self, key, val):
        # print(self.size(),self.capacity,self.load_thres,self.size() % self.capacity > self.load_thres)
        if self.load_factor():
            self.extend()
        pair = Pair(key, val)
        index = self.hash_key(key)
        for i in self.buckets[index]:

            if i.key == pair.key:
                i.val = pair.val
                return
        self.buckets[index].append(pair)
        self._size += 1

    def get(self, key: int) -> str:
        index = self.hash_key(key)
        for i in self.buckets[index]:

            if key == i.key:
                return i.val
        raise KeyError("没有key")

    def remove(self, key):
        try:
            if self.get(key):
                index = self.hash_key(key)
                s = 0
                for i in self.buckets[index]:
                    if key == i.key:
                        val = self.buckets[index].pop(s)
                        return val.val

                    s += 1

        except Exception as err:
            return err

    def extend(self):
        self._size = 0
        self.capacity = self.capacity * self.extend_ratio
        # print("s",self.capacity)
        buckets = self.buckets
        self.buckets = [[] for _ in range(self.capacity)]
        for bucket in buckets:
            for i in bucket:
                self.put(i.key, i.val)

    def key_set(self) -> list[int]:
        key_arr = []
        for _ in self.buckets:
            for i in _:
                if type(i) == Pair:
                    key_arr.append(i.key)
        return key_arr

    def val_set(self) -> list[int]:
        val_arr = []
        for _ in self.buckets:
            for i in _:
                if type(i) == Pair:
                    val_arr.append(i.val)
        return val_arr

    def entry_set(self) -> list[Pair]:
        arr = []
        for _ in self.buckets:
            for i in _:
                if type(i) == Pair:
                    arr.append([i.key, i.val])
        return arr


class ArraysHash2:
    """哈希：解决哈希冲突之线性探测

    通过哈希函数，计算出key，如果key值重复，就按固定的位向后移，直到出现空桶，再把元素放到空桶中。
    查找元素，也是计算出key。再按固定的位移值，进行移动。比较每一个桶中的key值"""
    def __init__(self):
        self._size = 0
        self.capacity = 4
        self.load_thres = 2 / 3
        self.extend_ratio = 2
        self.buckets = [0] * self.capacity
        self.TOMBSTONE = Pair(-1, "-1")

    def size(self):
        return self._size

    def is_extend(self):
        return (self.size() / self.capacity) > self.load_thres

    def index(self, key) -> int:
        return  ((key) + self.capacity) % self.capacity

    def hash_fun(self, key) -> int:
        return key % self.capacity

    def get(self, key):
        index = self.index(self.hash_fun(key))
        while 1:
            if(self.buckets[index] == 0):
                raise IndexError(f'没有该索引"{key}"')
            else :
                if self.buckets[index].key == key:
                    return self.buckets[index].val

            index += 1
            if(index > (self.capacity + index)):
                raise IndexError(f'没有该索引"{key}"')

    def put(self, key, val):
        pair = Pair(key, val)
        index = self.index(self.hash_fun(key))
        # print(self.is_extend())
        if self.is_extend():
            self.extend()
        i = 0
        while 1:
            # print(self.buckets[index])
            if(self.buckets[index] == 0):
                # print("1",self.buckets[index])
                self.buckets[index] = pair
                self._size += 1
                return
            elif self.buckets[index] == "-1":
                i = index
            elif self.buckets[index].key == key:
                # print(self.buckets[index].key)
                if(i):
                    self._size += 1
                    f = self.buckets[index]
                    self.buckets[index] = self.TOMBSTONE
                    self.buckets[i] = f
                    return
                else:
                    self._size += 1
                    self.buckets[index].key = val


            print("i=",i)


    def extend(self):
        buckets = self.buckets
        self.capacity = self.extend_ratio * self.capacity
        self.buckets = [0] * self.capacity
        self._size = 0
        for i in range(len(buckets)):
            if(buckets[i] == 0):
                pass
            elif buckets[i].key == "-1":
                self.buckets[i] = buckets[i]
            else:
                self.put(buckets[i].key, buckets[i].val)

    def entry_set(self):
        arr = []
        for i in range(self.capacity):
            if self.buckets[i] != 0:
                if self.buckets[i].key != -1:

                    arr.append((self.buckets[i].key, self.buckets[i].val))
        return arr
        pass

    def key_set(self):
        arr = []
        for i in range(self.capacity):
            if self.buckets[i] != 0:
                if self.buckets[i].key != -1:
                    arr.append(self.buckets[i].key)
        return arr
        pass

    def val_set(self):
        arr = []
        for i in range(self.capacity):
            if self.buckets[i] != 0 :
                if self.buckets[i].key != -1:
                    arr.append(self.buckets[i].val)
        return arr
        pass

    def remove(self, key):
        index = self.index(self.hash_fun(key))
        if(self.buckets[index] == 0):
            raise IndexError(f"没有索引值{key}")
        if self.buckets[index].key == key:
            return self.buckets[index].val
        pass


g = ArraysHash2()
g.put(1,"1")
g.put(2,"6")
# print(g.entry_set())
print(g.size())
print(",",g.capacity)
g.put(3,"1")
g.put(4,"5")
print(g.capacity)
print(g.entry_set())
print(g.size())
print(g.key_set())
print(g.val_set())
print(g.get(2))
# print(g.get(6))
print(g.remove(2))
print(g.entry_set())
